package com.sicheng.lc.周赛.分类.dp.线性;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/8/8 18:31
 */
public class 检查数组是否存在有效划分 {
    //https://leetcode.cn/problems/check-if-there-is-a-valid-partition-for-the-array/
    public boolean validPartition(int[] nums) {
        int n = nums.length;

        boolean[] dp = new boolean[n + 1];
        dp[0] = true;
        for (int i = 1; i <= n; i++) {
            int x = nums[i - 1];
            if (i >= 2) {
                dp[i] = nums[i - 2] == x && dp[i - 2];
            }
            if (dp[i])
                continue;
            if (i >= 3) {
                dp[i] |= dp[i - 3] && nums[i - 2] == nums[i - 3] && x == nums[i - 2];
                dp[i] |= dp[i - 3] && nums[i - 3] + 1 == nums[i - 2] && nums[i - 2] + 1 == x;
            }
        }
        return dp[n];
    }
}
